﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace BuildOptimizer
{
    class BoDecisionTree
    {
        //GUI functionality
        private GUI _GUI = null;
        private bool _cancelFlag = false;
        public void registerGUI(GUI GUI)
        {
            _GUI = GUI;
        }
        public void cancelAllWork()
        {
            _cancelFlag = true;
        }

        //thread safety
        private ManualResetEvent[] _resetEvents;
        private object _lockAddBuildOrder = new object();
        private object _lockUpdateStatistics = new object();

        private BoDecisionNode _root = null;
        private List<BoDecisionNode> _startNodes = new List<BoDecisionNode>();

        private BoDecisionAnalyzer _analyzer = null;
        public BoDecisionTree(BoDecisionAnalyzer analyzer)
        {
            _analyzer = analyzer;
            _root = new BoDecisionNode(null, new BoCommandStartFromRoot());
            _root.executeCommand(_analyzer.goal);
        }

        public void buildAndTraverse(int nbThreadsDesired)
        {
            createStartNodes(nbThreadsDesired);

            _resetEvents = new ManualResetEvent[_startNodes.Count];
            for (int i = 0; i < _startNodes.Count; i++)
            {
                int startNodeIndex = i;
                _resetEvents[i] = new ManualResetEvent(false);

                //we don't pass i directly, because casting it to object creates a copy on the
                //heap. If we were to pass i itself, then both threads would contain a ref
                //to the same i object. We create a startNodeIndex var to avoid this.
                ThreadPool.QueueUserWorkItem(new WaitCallback(buildAndTraverseSubtree), (object)startNodeIndex);
            }
            WaitHandle.WaitAll(_resetEvents);
        }
        private void createStartNodes(int nbThreadsDesired)
        {
            //keep track of how the number of start nodes varies
            _startNodes.Add(_root.cloneWithoutChildren());
            List<int> nbStartNodes = new List<int>();
            nbStartNodes.Add(1);

            while (0 < _startNodes.Count && _startNodes.Count < nbThreadsDesired)
            {
                //create all children across all times of the first start node
                while (createChildren(_startNodes[0]))
                {
                    //copy the children of a given time to startNodes
                    for (int i = 0; i < _startNodes[0].children.Count; i++)
                    {
                        _startNodes.Add(_startNodes[0].children[i]);
                    }

                    //we replace the original start node. Since the node will change
                    //its state when advancing in time, this would othewise cause
                    //children created at an earlier time to now point at a node that
                    //has a later time than themselves.
                    _startNodes[0] = _startNodes[0].cloneWithoutChildren();
                }

                //remove the parent of these children from the list
                _startNodes.RemoveAt(0);

                //keep track of number of start nodes
                nbStartNodes.Add(_startNodes.Count);
            }

            //find best actual number of threads to schedule
            bool found = false;
            int nbActualThreads = nbStartNodes[0];
            for (int i = 0; i < nbStartNodes.Count && !found; i++)
            {
                if (nbStartNodes[i] >= nbThreadsDesired)
                {
                    nbActualThreads = nbStartNodes[i];
                    found = true;
                }
            }

            //prepare startNodes according to actual number of threads to schedule
            _startNodes.Clear();
            _startNodes.Add(_root.cloneWithoutChildren());

            while (_startNodes.Count < nbActualThreads)
            {
                while (createChildren(_startNodes[0]))
                {
                    for (int i = 0; i < _startNodes[0].children.Count; i++)
                    {
                        _startNodes.Add(_startNodes[0].children[i]);
                    }

                    _startNodes[0] = _startNodes[0].cloneWithoutChildren();
                }

                _startNodes.RemoveAt(0);
            }

            string output = string.Format("number of threads active: {0}", nbActualThreads);
            _GUI.Invoke(new updateOutputTextDelegate(_GUI.updateOutputText), new object[] { output });
        }
        private void buildAndTraverseSubtree(object startNodeIndex)
        {
            BoDecisionNode startNode = _startNodes[(int)startNodeIndex];
            BoDecisionNode currentNode = startNode;

            do
            {
                if (currentNode.hasNoChildren())
                {
                    bool continueFurtherDown = createChildren(currentNode);
                    if (continueFurtherDown)
                    {
                        currentNode = currentNode.leftChild;
                    }
                    else
                    {
                        lock (_lockUpdateStatistics)
                        {
                            _analyzer.updateStatistics();
                        }
                        currentNode = removeNode(currentNode, startNode);
                    }
                }
                else
                {
                    currentNode = currentNode.leftChild;
                }
            } while (currentNode != startNode.parent && _cancelFlag == false);

            _resetEvents[(int)startNodeIndex].Set();
        }

        private BoDecisionNode removeNode(BoDecisionNode n, BoDecisionNode startNode)
        {
            if (n.parent != startNode.parent)
            {
                n.parent.removeChild(n);
                return n.parent;
            }
            return startNode.parent;
        }
        private bool createChildren(BoDecisionNode n)
        {
            //wait for new commands
            bool isOutOfTime = false;
            bool isGoalAchieved = false;
            List<BoCommand> newPossibleCommands;

            while (true)
            {
                lock (_lockAddBuildOrder)
                {
                    //if we're out of time
                    isOutOfTime = (!_analyzer.isFastEnough(n.gameState) || !_analyzer.goal.isReachableBy(n.gameState));
                    if (isOutOfTime)
                    {
                        return false;
                    }

                    //if goal is achieved
                    isGoalAchieved = _analyzer.goal.isSatisfiedBy(n.gameState);
                    if (isGoalAchieved)
                    {
                        BoBuildOrder buildOrder = calcBuildOrder(n);
                        _analyzer.addBuildOrder(buildOrder);
                        return false;
                    }
                }

                //create children
                newPossibleCommands = findNewPossibleCommands(n);
                if (newPossibleCommands.Count > 0)
                {
                    for (int i = 0; i < newPossibleCommands.Count; i++)
                    {
                        BoDecisionNode child = new BoDecisionNode(n, newPossibleCommands[i], n);
                        child.executeCommand(_analyzer.goal);
                        n.addChild(child);
                    }
                    return true;
                }

                n.gameState.tick(n);
            }
        }

        private List<BoCommand> findNewPossibleCommands(BoDecisionNode n)
        {
            List<BoCommand> newPossibleCommands = _analyzer.findPossibleCommands(n);

            //set duplicate commands to null
            for (int i = 0; i < newPossibleCommands.Count; i++)
            {
                for (int j = 0; j < n.childrenCommandCodeLog.Count; j++)
                {
                    if (newPossibleCommands[i] != null && newPossibleCommands[i].getCommandCode() == n.childrenCommandCodeLog[j])
                    {
                        newPossibleCommands[i] = null;
                    }
                }
            }
            //remove null values
            for (int i = (newPossibleCommands.Count - 1); i >= 0; i--)
            {
                if (newPossibleCommands[i] == null)
                {
                    newPossibleCommands.RemoveAt(i);
                }
            }

            return newPossibleCommands;
        }
        private BoBuildOrder calcBuildOrder(BoDecisionNode endNode)
        {
            BoBuildOrder buildOrder = new BoBuildOrder();

            //store all relevant nodes for the build order
            List<BoDecisionNode> buildOrderNodes = new List<BoDecisionNode>();
            BoDecisionNode node = endNode;
            while (node != null)
            {
                buildOrderNodes.Add(node);
                node = node.parent;
            }

            //loop over these nodes and collect their decisions
            for (int i = (buildOrderNodes.Count() - 1); i >= 0; i--)
            {
                BoDecision d = new BoDecision(buildOrderNodes[i]);
                buildOrder.addDecision(d);
            }

            return buildOrder;
        }
    }
}
